package 剑指offer;

public class _26树的子结构 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null){
            return false;
        }
        //1.先找起始位置
        boolean result = false;
        if (A.val == B.val){
            result = IsSameChild(A, B);//判定两棵树的左右子树是否相等
        }
        if(result != true){
            result = isSubStructure(A.left,B);
        }
        if (result != true){
            result = isSubStructure(A.right, B);
        }
        return result;
    }
    //2.比较左右子树是否相等
    private boolean IsSameChild(TreeNode root1, TreeNode root2) {
        //若为空，说明这棵树比较完了，就是相同的
        if(root2 == null){
            return true;
        }
        if(root1 == null){
            return false;
        }

        if(root1.val != root2.val){
            return false;
        }
        //走到这里说明当前节点是相等的
        return IsSameChild(root1.left, root2.left) && IsSameChild(root1.right, root2.right);
    }
}
